package com.future;

/**
 * Description:
 * 假设文件系统如下图所示：
 * 这里将 dir 作为根目录中的唯一目录。dir 包含两个子目录 subdir1 和 subdir2 。subdir1 包含文件 file1.ext 和子目录 subsubdir1；subdir2
 * 包含子目录 subsubdir2，该子目录下包含文件 file2.ext 。
 * 在文本格式中，如下所示(⟶表示制表符)：
 * dir
 * ⟶ subdir1
 * ⟶ ⟶ file1.ext
 * ⟶ ⟶ subsubdir1
 * ⟶ subdir2
 * ⟶ ⟶ subsubdir2
 * ⟶ ⟶ ⟶ file2.ext
 * 如果是代码表示，上面的文件系统可以写为 "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext" 。
 * '\n' 和 '\t' 分别是换行符和制表符。
 * 文件系统中的每个文件和文件夹都有一个唯一的 绝对路径 ，即必须打开才能到达文件/目录所在位置的目录顺序，所有路径用 '/' 连接。
 * 上面例子中，指向 file2.ext 的绝对路径是 "dir/subdir2/subsubdir2/file2.ext" 。每个目录名由字母、数字和/或空格组成，
 * 每个文件名遵循 name.extension 的格式，其中名称和扩展名由字母、数字和/或空格组成。
 * 给定一个以上述格式表示文件系统的字符串 input ，返回文件系统中 指向文件的最长绝对路径 的长度。 如果系统中没有文件，返回0。
 * 示例 1：
 * 输入：input = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
 * 输出：20
 * 解释：只有一个文件，绝对路径为 "dir/subdir2/file.ext" ，路径长度 20
 * 路径 "dir/subdir1" 不含任何文件
 * 示例 2：
 * 输入：input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
 * 输出：32
 * 解释：存在两个文件：
 * "dir/subdir1/file1.ext" ，路径长度 21
 * "dir/subdir2/subsubdir2/file2.ext" ，路径长度 32
 * 返回 32 ，因为这是最长的路径
 * 示例 3：
 * 输入：input = "a"
 * 输出：0
 * 解释：不存在任何文件
 * 示例 4：
 * 输入：input = "file1.txt\nfile2.txt\nlongfile.txt"
 * 输出：12
 * 解释：根目录下有 3 个文件。
 * 因为根目录中任何东西的绝对路径只是名称本身，所以答案是 "longfile.txt" ，路径长度为 12
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-absolute-file-path
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2021/11/2 15:17
 */
public class Solution_lengthLongestPath_388 {

    public static void main(String[] args) {
        String input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
        input = "dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsundir2\n\t\t\tfile2.ext";
        input = "dir\n\tsubdir1\n\t\tfile1.ext\n\txf\n\t\tt.ext\n\t\t\ta.ex";
        //input = "dir/subdir2/subsubdir2/file2.ext";
        input = "file1.txt\nfile2.txt\nlongfile.txt";
        System.out.println("我的：" + lengthLongestPath(input));
        System.out.println("答案：" + lengthLongestPath_v2(input));
    }

    public static int lengthLongestPath_v2(String input) {
        if (input.length() == 0) {
            return 0;
        }
        int res = 0;
        int[] sum = new int[input.length() + 1];    //从1开始，第0层就是0

        for (String s : input.split("\n")) {
            int level = s.lastIndexOf('\t') + 2;    // 计算当前在第几层（从第一层开始，没有\t就是第一层）
            int len = s.length() - (level - 1);     // 计算当前这一行的长度
            if (s.contains(".")) {
                res = Math.max(res, sum[level - 1] + len);
            } else {
                sum[level] = sum[level - 1] + len + 1;  //是目录，要+1，目录有个/的
            }
        }
        return res;
    }

    /**
     * 思路：
     * 注意，路径计算的是到文件的长度（.exe|.txt|xx.bbs，所以：a\n\t\b\n\\tc\n\td没有到文件的返回都是0）
     * 步骤：
     * 1、根据"\n"拆开成字符串数组，并创建长度为数组长度的数组，用于存储当前文件路径各个阶段的长度
     * 2、遍历每个字符串，根据每个字符串的最后"\t"下标+1判断处于第n个目录下
     * 3、判断是改字符串是文件还是目录
     * 3.1 是文件
     * 计算长度
     * 3.2 是目录
     * 更新数组当前第n个下标对应字符串的总长度（arr[n] = arr[n-1]+当前字符长度+1）
     *
     * @param input
     * @return
     */
    public static int lengthLongestPath(String input) {
        if (null == input || input.length() == 0) return 0;
        String[] split = input.split("\n");
        int[] arr = new int[split.length];
        int result = 0;
        for (int i = 0; i < split.length; i++) {
            String str = split[i];
            int level = str.lastIndexOf("\t") + 1;
            int length = str.length() - level;
            if (split[i].contains(".")) {
                /**
                 * 来到了文件,计算长度
                 */
                if (level == 0) {
                    result = Math.max(result, length);
                } else {
                    result = Math.max(result, arr[level - 1] + length);
                }
            } else {
                /**
                 * 继续是文件夹(注意，这里+1是由于还隐含着"/"，长度为1
                 * 因为最终格式如：a/b/c但是这里length未包含"/"，所以手动+1)
                 */
                if (level == 0) {
                    arr[level] = length + 1;
                } else {
                    // 数组第n个下标对应的值是数组前一个下标长度+1（即"/"的长度）+当前字符串长度
                    arr[level] = arr[level - 1] + length + 1;
                }
            }
        }
        return result;
    }

}
